package Tree;

import java.util.*;

public class PostorderTraversal {
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (null == root) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        HashMap<TreeNode, Boolean> visited = new HashMap<>();

        stack.push(root);
        visited.put(root, false);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            if (visited.get(cur)) {
                res.add(cur.val);
                stack.pop();
            } else {
                visited.put(cur, true);
                if (cur.right != null) {
                    stack.push(cur.right);
                    visited.put(cur.right, false);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                    visited.put(cur.left, false);
                }
            }
        }


        return res;
    }

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (null == root) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);

            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }

        }
        Collections.reverse(res);
        return res;
    }

}
